K. Сортировка слиянием

Гоше дали задание написать красивую сортировку слиянием. Поэтому Гоше обязательно надо реализовать отдельно функцию merge и функцию merge_sort.
Функция merge принимает два отсортированных массива, сливает их в один отсортированный массив и возвращает его. Если требуемая сигнатура имеет вид merge(array, left, mid, right), то первый массив задаётся полуинтервалом 
[left, mid) массива array, а второй – полуинтервалом [mid, right) массива array.
Функция merge_sort принимает некоторый подмассив, который нужно отсортировать. Подмассив задаётся полуинтервалом — его началом и концом. Функция должна отсортировать передаваемый в неё подмассив, она ничего не возвращает.
Функция merge_sort разбивает полуинтервал на две половинки и рекурсивно вызывает сортировку отдельно для каждой. Затем два отсортированных массива сливаются в один с помощью merge.
Заметьте, что в функции передаются именно полуинтервалы 
[begin, end), то есть правый конец не включается. Например, если вызвать merge_sort(arr, 0, 4), где 
arr =
[4, 5, 3, 0, 1, 2]
, то будут отсортированы только первые четыре элемента, изменённый массив будет выглядеть как 
arr = [0 , 3, 4, 5, 1, 2].
Реализуйте эти две функции.
Мы рекомендуем воспользоваться заготовками кода для данной задачи, расположенными по ссылке.

Формат ввода
Передаваемый в функции массив состоит из целых чисел, не превосходящих по модулю 
10 в степени 9. Длина сортируемого диапазона не превосходит 10 в степени 5.

Формат вывода
Python

merge(arr: list, left: int, mid: int, right: int) -> array <br>
merge_sort(arr: list, left: int, right: int) -> None